Consider a large scale network where parties or participants exchange secure communication using cryptographic keys and certificates. Three major requirements for such secure network communication are communication integrity protection, anonymity of honest participants and traceability of misbehaving participants. Communication integrity protection can be achieved appending to each message a digital signature. When a given signed message might have been produced by all or many of the parties in the infrastructure, each party is virtually anonymous. Traceability refers to the ability to find which participants produced a given malicious signed message.
Such secure communications can occur where each pair of key and certificate that may be used is actually shared by a large number of parties. While such key sharing strategies may guarantee satisfactory levels of anonymity, they automatically make it hard to trace or identify any party that, while using pairs of cryptographic keys and certificates, delivers messages containing malicious activity. Hence, a major problem with this scheme relates to the traceability requirement. This is especially important in the case of repeated malicious activity from these parties, where re-keying the keys associated with malicious activity does not seem to help in solving the problem, as the attacker or malicious party is allowed to continue malicious activity with the newly obtained key and still remain undetected.
For example, if the attacker sends a single malicious message, then the attacker can be traced at best as one of the group of clients or participants that share the attacking key. However, this group contains, on average, the total number of participants times the total number of groups, divided by the number of members of a group, so that the group can be very large, especially if the number of participants is very large. Accordingly, this traceability strategy is not really effective. Even worse, in typical attacks consisting of several malicious messages, an attacker can decide to use the following strategy: first, it uses an arbitrary signature key to send the first malicious message; afterwards, this message is detected to be malicious, so that the arbitrary signature key is revoked and replaced with a fresh one. Then, the attacker will attack again using precisely the fresh signature key because the attacker is not obliged to randomly choose the verification key to obtain the next attacking message. The result is that the traceability does not improve and the attacker will be able to send several attacking messages without increasing its already low traceability.
The solution in the prior art to detecting malicious parties in secure communications requires eliminating the anonymity of each party in the system. Previously studied and somewhat related models of this problem include broadcast or multicast encryption (see, e.g., R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor and B. Pinkas, Multicast Security: A Taxonomy and Efficient Authentication, in Proc. of Infocomm 1999, and A. Fiat and M. Naor, Broadcast Encryption, in Proc. Of Crypto 1993, LNCS, Springer-Verlag.), group signatures (introduced in D. Chaum and E. van Heist, Group Signatures, in Proc. of Eurocrypt 1991, LNCS, Springer-Verlag.) and ring signatures (introduced in R. Rivest, A. Shamir, and Y. Tauman, How to leak a secret, in Proc. of Asiacrypt 2001, LNCS, Springer-Verlag.). Other variations proposed and analyzed by several research groups, such as J. Garay, J. Staddon, and A. Wool, Long-live Broadcast Encryption, in Proc. of CRYPTO 2000, LNCS, Springer-Verlag., L. Eschenauer and V. D. Gligor, A Key-Management Scheme For Distributed Sensor Networks, in Proc. of ACM, and S. Tengler, S. Andrews, and R. Heft, Digital Certificate Pool, U.S. Patent Application Publication No. 2007/0223702, also illustrate various contexts and models, but do not effectively achieve anonymity and traceability.
Another studied area in the cryptography and software protection literature is called “Traitor Tracing”, which does guarantee distribution of “valid” keys to parties in a way that if some “traitors” help a new unauthorized party to come up with a valid key, then one of the “traitors” is detected. However, this key distribution strategy does not guarantee any anonymity to the parties.
Accordingly, a method that allows the parties to achieve and maintain the same satisfactory level of anonymity and yet allows an authority to detect which parties are responsible for sending messages with malicious activity is needed.